package linked;

/**
 * 25. K 个一组翻转链表
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * <p>
 * k 是一个正整数，它的值小于或等于链表的长度。
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 * <p>
 * 示例 2：
 * 输入：head = [1,2,3,4,5], k = 3
 * 输出：[3,2,1,4,5]
 */
public class Problem_25 {

    /**
     * 方法一 : 模拟
     * 每 K个节点一组，组内进行链表翻转
     */
    public ListNode reverseKGroup_1(ListNode head, int k) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode prev = dummyHead;

        while (true) {
            // 检查剩余节点 是否有k个，不足则返回
            ListNode tail = prev;
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                if (tail == null) {
                    return dummyHead.next;
                }
            }

            // 翻转k个节点
            ListNode node = prev.next, next;
            for (int i = 0; i < k - 1; i++) {
                next = node.next;
                node.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = node;
        }
    }

    /**
     * 方法二 : 递归解法
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode nextHead = head;
        //找到本组待翻转部分 尾节点的下一个节点
        for (int i = 0; i < k; i++) {
            if (nextHead == null) {
                return head;
            }
            nextHead = nextHead.next;
        }

        ListNode pre = null;
        ListNode node = head;
        while (node != nextHead) {
            ListNode next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        //尾节点指向下一个翻转的头节点
        head.next = reverseKGroup(nextHead, k);
        return pre;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
